// DP
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> vec;
        return func2(vec, n, n);
    }
    vector<string> func2(vector<string> vec, int left, int right)
    {
        if(left + right == 0)
            return vec;
        if(vec.empty())
            return func2({"("}, left - 1, right);
        if (left == right)
        {
            for(int i = 0; i < vec.size(); i++)
                vec[i] += "(";
            return func2(vec, left - 1, right);
        }
        if(left == 0 && right != 0)
        {
            for(int i = 0; i < vec.size(); i++)
                vec[i] += ")";
            return func2(vec, left, right - 1);
        }
        if(left != 0 && right > left)
        {
            vector<string> v1 = vec;
            vector<string> v2 = vec;
            for(int i = 0; i < vec.size(); i++)
            {
                v1[i] += "(";
                v2[i] += ")";
            }
            v1 = func2(v1, left - 1, right);
            v2 = func2(v2, left, right - 1);
            v1.insert(v1.end(), v2.begin(), v2.end());
            return v1;
        }
    }
};
